/*
  this link list program can be used to form table for compression
  @ vishwajeet dusane
  What this program does
	 -accept file name from user
	 -build table i.e. occurence of each char in the file
	 -sort them according to the number of char in file in descending order
*/

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
int search(struct node **,char );
void display(struct node *);
void create(struct node **,char);
void SortTable(struct node **);

struct node
{
  char ch;
  int counter;
  struct node *next;
};

void main()
{
	struct node *head=NULL;
	int choice,result;
	char ch;
	char fname[30];
	FILE *fp;
	printf("Enter File Name:");
	scanf("%s",fname);

	  fp=fopen(fname,"r");

	while((ch=fgetc(fp))!=EOF)
	{
	 result=search(&head,ch);/*whether the char is in the table or not
							   if it is in then no need to add that in
							   the table search will automatically
							   increment its count
							   */

	 if(result!=0)
	 create(&head,ch);
	}
	display(head);

	 SortTable(&head);   /*This function can sort the nodes according to
						   the occurrences of a charcter
						 */
	 clrscr();
	   display(head);    /*this function will display the sorted nodes
							can be used for display (those which r not sorted)
							sort it in descending order
						 */
   }


void create(struct node **head,char ch)
 {
   struct node *temp=*head;

	if(*head==NULL)
	  {
	   *head=(struct node *)malloc(sizeof(struct node));
	  (*head)->next=NULL;
	(*head)->ch=ch;
	(*head)->counter=1;
	   }
	  else
	  {
	  temp=*head;
	  while(temp->next!=NULL)
	  temp=temp->next;
	  temp->next=(struct node *)malloc(sizeof(struct node));

	  temp=temp->next;
	  temp->next=NULL;
	 temp->ch=ch;
	 temp->counter=1;
	   }
 }
void  display(struct node *temp)
 {

	while(temp!=NULL)
	{
	 printf("%c\t%d \n",temp->ch,temp->counter);
	 temp=temp->next;
	 }
	 getch();
 }

int search(struct node **head,char ch)
{
   struct node *temp=*head;

	if(*head==NULL)
	  {
	  return 1;
	  }
	  else
	  {
	 temp=*head;
	  while(temp!=NULL)
	  {
		if(temp->ch==ch)
		{
		 temp->counter++;
		 return 0;
		}
	  temp=temp->next;
	  }
	   }
  return 1;
}

void SortTable(struct node **head)
{
	struct node *temp,*temp1;
	int tempCounter,tempCh;
	int i,j;

  if(*head==NULL)
	return;
  else
  {
	temp=*head;
   while(temp!=NULL)
  {
	 temp1=*head;
	while(temp1!=NULL)
	{
	   if( ( temp1 -> counter ) < ( temp -> counter ) )
		{
		 tempCounter = temp1 -> counter;
		 temp1 -> counter = temp -> counter;
		 temp -> counter = tempCounter;
		 tempCh = temp1 -> ch;
		 temp1 -> ch = temp -> ch;
		 temp -> ch = tempCh;
		}
		 temp1 = temp1 -> next;
	}
	temp=temp->next;
  }
}
}
